package 动态规划;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-09-26
 **/

public class No140单词拆分II {

    /**
     * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
     *
     * 说明：
     * 分隔时可以重复使用字典中的单词。
     * 你可以假设字典中没有重复的单词。
     * 示例 1：
     * 输入:
     * s = "catsanddog"
     * wordDict = ["cat", "cats", "and", "sand", "dog"]
     * 输出:
     * [
     *   "cats and dog",
     *   "cat sand dog"
     * ]
     * 示例 2：
     * 输入:
     * s = "pineapplepenapple"
     * wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
     * 输出:
     * [
     *   "pine apple pen apple",
     *   "pineapple pen apple",
     *   "pine applepen apple"
     * ]
     * 解释: 注意你可以重复使用字典中的单词。
     * 示例 3：
     * 输入:
     * s = "catsandog"
     * wordDict = ["cats", "dog", "sand", "and", "cat"]
     * 输出:
     * []
     */

    private StringBuilder sb = new StringBuilder();
    private List<String> ans = new ArrayList<>();

    private void dfs(String s,Set<String> wordSet,int index){
        if(index == s.length()){
            sb.setLength(sb.length() - 1);
            ans.add(sb.toString());
            return;
        }
        for(int i = index;i < s.length();i++){
            String word = s.substring(index,i + 1);
            if(wordSet.contains(word)){
                int len = sb.length();
                sb.append(word).append(' ');
                dfs(s,wordSet,i + 1);
                sb.setLength(len);
            }
        }
    }

    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        dfs(s,wordSet,0);
        return ans;
    }

    public static void main(String[] args) {
        No140单词拆分II n = new No140单词拆分II();
        List<String> result = n.wordBreak("pineapplepenapple", Arrays.asList("apple", "pen", "applepen", "pine", "pineapple"));
        System.out.println(JSON.toJSONString(result));
    }

}
